package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //目标和
        class Solution {
            int result;  // 记录命中 target 的表达式数量
            int len;     // 数组长度
            int t;       // 目标 target

            public int findTargetSumWays(int[] nums, int target) {
                this.t = target;
                this.len = nums.length;
                result = 0;
                dfs(nums, 0, 0);
                return result;
            }

            // 回溯：在位置 pos 选择 +nums[pos] 或 -nums[pos]
            private void dfs(int[] nums, int pos, int curSum) {
                if (pos == len) {
                    if (curSum == t) result++;
                    return;
                }
                dfs(nums, pos + 1, curSum + nums[pos]); // 选择 +
                dfs(nums, pos + 1, curSum - nums[pos]); // 选择 -
            }
        }

        //数组总和
        class Solution2 {
            List<List<Integer>> ret;
            List<Integer> path;
            int t;

            public List<List<Integer>> combinationSum(int[] c, int _t) {
                ret = new ArrayList<>();
                path = new ArrayList<>();
                t = _t;

                Arrays.sort(c); // 升序：启用“超目标即剪枝”的 break

                dfs(c, 0, 0);
                return ret;
            }

            // 回溯：从下标 pos 开始选择，当前和为 cur
            public void dfs(int[] nums, int pos, int cur) {
                if (cur == t) {                 // 命中目标，收集一份解
                    ret.add(new ArrayList<>(path));
                    return;
                }

                for (int i = pos; i < nums.length; i++) {
                    int v = nums[i];
                    if (cur + v > t) break;     // 关键剪枝：已排序，后面的更大，直接停止本层循环

                    path.add(v);
                    dfs(nums, i, cur + v);      // 可重复使用同一元素，因此下一层仍从 i 开始
                    path.remove(path.size() - 1); // 回溯
                }
            }
        }
    }
}